package demo2;

class Solution1 {

    public boolean isSameTree(TreeNode p,TreeNode q){
        if((p==null&&q!=null)||(p!=null&&q==null)) return false;
        if(p==null&&q==null) return true;
        if(p.val!=q.val) return false;
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null) return false;
        //判断一棵树是否是另一颗的子
        if(isSameTree(root,subRoot)){
            return true;
        }
        return (isSubtree(root.left,subRoot))|| (isSubtree(root.right,subRoot));
    }
}

class Solution4 {
    public int height(TreeNode root){
        if(root==null) return 0;
        //左子树的高度与右子树的高度最大值+1
        int left = height(root.left);
        int right = height(root.right);
        return left>right?left+1:right+1;
    }

    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int left = height(root.left);
        int right = height(root.right);
        return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
}

class Solution3 {
    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if((p==null&&q!=null)||(p!=null&&q==null)){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left);
    }

    public boolean isSymmetric(TreeNode root) {
        return isSymmetricChild(root.left,root.right);
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(p==root) return p;
        if(q==root) return q;
        //p在root的左侧，q在root的右侧
        //此时p,q只能在root的左侧或者是右侧
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        if(leftTree!=null){
            return leftTree;
        }
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(rightTree!=null){
            return rightTree;
        }
        return null;
    }
}
public class TestDemo1 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode nodR1 = new TreeNode(3);
        TreeNode nodR2 = new TreeNode(5);
        TreeNode nodR3 = new TreeNode(1);
        TreeNode nodR4 = new TreeNode(6);
        TreeNode nodR5 = new TreeNode(2);
        TreeNode nodR6 = new TreeNode(0);
        TreeNode nodR7 = new TreeNode(8);
        TreeNode nodR8 = new TreeNode(7);
        TreeNode nodR9 = new TreeNode(4);

        nodR1.left = nodR2;
        nodR1.right = nodR3;
        nodR2.left = nodR4;
        nodR2.right = nodR5;
        nodR3.left = nodR6;
        nodR3.right = nodR7;
        nodR5.left = nodR8;
        nodR5.right = nodR9;
        System.out.println(solution.lowestCommonAncestor(nodR1,nodR5,nodR9));
    }
}
